Papers with exponential reduction
RNNs can generate bounded hierarchical languages with optimal memory (2020.emnlp-main)
Copied to clipboard
| Challenge: | Existing studies have shown that RNNs can efficiently generate bounded hierarchical languages with high syntactic fidelity, but their success is not well-understood theoretically. |
| Approach: | They propose a language of well-nested brackets and m-bounded nesting depth . they prove that an RNN with O(m log k) hidden units suffices, an exponential reduction in memory, by an explicit construction. |
| Outcome: | The proposed language is well-nested brackets and has m-bounded nesting depth . it shows that an RNN with O(m log k) hidden units suffices, an exponential reduction in memory, by an explicit construction. |